#include "Ejercicio1.h"

/***********************************eje**************************************/

Ejercicio1::eje::eje()
{
    origen = 0;
    destino = 0;
}

Ejercicio1::eje& Ejercicio1::eje::operator=( const eje & otra )
{
    origen = otra.origen;
    destino = otra.destino;
    return *this;
}

/******************************************************************************/

Ejercicio1::Ejercicio1()
{
}

Ejercicio1::~Ejercicio1()
{
}

void Ejercicio1::execute( const string& in, const string& out )
{
	ifstream fin( in.c_str(), ios::in );
	ofstream fout( out.c_str(), ios::out );
	
	if( fin.good() && fout.good() )
	{
		stringstream ss;
		string linea, salida = "";
		int participantes = 0, partidos = 0;
		unsigned int j;
		list<int> res;
		
		//por cada caso
		while( getline( fin, linea ) && linea != "0 0" )
		{
            j = 0;
			
			 while( j < linea.length() && linea[j] != ' ' )
			 	j++;
			 	
			participantes = atoi( linea.substr( 0, j ).c_str() );
			partidos = atoi( linea.substr( j+1, linea.length() ).c_str() );
			
			Ejercicio1::eje p[ partidos ];
			
			for( int i = 0; i < partidos && getline( fin, linea ) && linea != "0 0"; i++ )
    		{	
                j = 0;
    		
    			 while( j < linea.length() && linea[j] != ' ' )
    			 	j++;
    		 	
                p[i].origen = atoi( linea.substr( 0, j ).c_str() );
                p[i].destino = atoi( linea.substr( j+1, linea.length() ).c_str() );
    		}
    		
    		res = quienesPuedenGanar( participantes, partidos, p );
    		
    		salida+= salida == "" ? "" : "\n";
			ss.str("");
			ss << (int) res.size();
			salida+= ss.str();
    		
    		for( list<int>::iterator it = res.begin(); it != res.end(); it++ )
    		{
                salida+= " ";
    			ss.str("");
    			ss << *it;
    			salida+= ss.str();
            }
        }
        
        fout.write( salida.c_str(), salida.length() );
	}
	
	if( fin.good() )
		fin.close();
	if( fout.good() )
		fout.close();
}

list<int> Ejercicio1::quienesPuedenGanar
( const int participantes, const int partidos, Ejercicio1::eje ejes[] )
{   
    //resultado
    list<int> res;
    
    //contador auxiliar
    int i;
    
    //profundidad acumulada del dfs
    int p = 0;
    //contador de componentes fuertemente conexas
    int c = 0;
    //indica a que componente fuertemente conexa pertenece c/participante
    int componente[participantes];
    //indica low de cada participante
    int low[participantes];
    //indica profundidad de cada participante
    int profundidad[participantes];
    //indica si un participante fue marcado
    bool participante_marcado[participantes];
    //indica si un participante esta en la pila
    bool participante_apilado[participantes];
    
    //inicializo todo
    for( i = 0; i < participantes; i++ )
    {
        componente[i] = -1;
    	participante_marcado[i] = false;
    	participante_apilado[i] = false;
    	low[i] = 0;
    	profundidad[i] = 0;
    }
    
    //armo las listas de los ejes de los cuales el participante es origen
    list<int> hijos[participantes];
    
    for( i = 0; i < partidos; i++ )
    {
    	hijos[ ejes[i].origen - 1 ].push_front( ejes[i].destino - 1 );
    }
    
    //para ir acumulando los participantes
    list<int> pila;
    
    //voy visitando cada participante
    //tarjan arma las componentes fuertemente conexas (CFCs) que hay
    //haciendo DFS
    for( i = 0; i < participantes; i++ )
    {
        //inicio desde arriba otro DFS
        //la profundidad debe empezar en 0
        p = 0;
        
        //si todavia no lo visite
        if( !participante_marcado[i] )
        {
        	tarjan
        	(
        		i,
        		ejes,
        		hijos,
        		participante_marcado,
        		participante_apilado,
        		low,
        		profundidad,
                componente,
        		pila,
        		p,
        		c
        	);
        }
    }
    
    //ahora se CFCs conexas hay
    //y se en cual esta cada participante
    //quiero ver si hay una CFC con grado de entrada cero
    bool din_cero[c];
    
    //por cada CFC
    for( i = 0; i < c; i++ )
    {
        din_cero[c] = true;
    }
    
    //recorro cada participante
    list<int>::iterator it;
    
    for( i = 0; i < participantes; i++ )
    {
        //recorro cada hijo
        for( it = hijos[i].begin(); it != hijos[i].end(); it++ )
        {
            //si esta en distinta CFC que su padre
            if( componente[i] != componente[*it] )
            {
                //la CFC del hijo no tiene grado de entrada cero
                din_cero[ componente[*it] ] = false;
            }
        }
    }
    
    //ahora me fijo que CFC tiene grado de entrada cero
    int cant_din_cero = 0, comp_din_cero;
    
    for( i = 0; i < c; i++ )
    {
        //si tiene grado de entrada cero
        if( din_cero[i] )
        {
            //guardo cual es
            comp_din_cero = i;
            //aumento la cantidad que encontre
            cant_din_cero++;
        }
    }
    
    //si hay una sola de grado cero hay solucion
    //la solucion son todos los participantes de esa CFC
    if( cant_din_cero == 1 )
    {
        //por cada participante
        for( i = 0; i < participantes; i++ )
        {
            //si esta en la CFC indicada
            if( componente[i] == comp_din_cero )
                res.push_back(i+1);
        }
    }
    
    //devuelvo los participantes que pueden ganar
    return res;
}

void Ejercicio1::tarjan
(
	int participante,
	Ejercicio1::eje ejes[],
	list<int> hijos[],
	bool participante_marcado[],
	bool participante_apilado[],
	int low[],
	int profundidad[],
	int componente[],
	list<int>& pila,
	int& p,
	int& c
){
	//agrego al participante a la pila
	pila.push_front(participante);
	//indico que visite al participante
	participante_marcado[participante] = true;
	//indico que el participante esta actualmente en la pila
	participante_apilado[participante] = true;
	//defino la profundidad del participante
	profundidad[participante] = p;
	//aumento la profundidad
	p++;
	
	low[participante] = profundidad[participante];
	
	//recorro los participantes a los cuales puede ganar
	list<int>::iterator it, it2;
	
	for( it = hijos[participante].begin(); it != hijos[participante].end(); it++ )
	{
		//si el participante aun no fue visitado
		if( !participante_marcado[*it] )
		{
            //sigo con el dfs
			tarjan
			(
				*it,
				ejes,
				hijos,
				participante_marcado,
				participante_apilado,
				low,
				profundidad,
                componente,
        		pila,
        		p,
        		c
			);
			
			low[participante] = low[participante] < low[*it] ? 
				low[participante] : low[*it];
		}
		//si la profundidad del hijo es mas chica
		//y si el hijo ya estaba en la pila
		else if( profundidad[*it] < profundidad[participante] && participante_apilado[*it] )
		{
			low[participante] = low[participante] < profundidad[*it] ? 
				low[participante] : profundidad[*it];
		}
	}
	
	if( low[participante] == profundidad[participante] )
	{
		//saco de arriba de la pila
		it = pila.begin();
				
		//si habia algo
		if( it != pila.end() )
		{
            //indico en que componente quedo ese participante
            componente[*it] = c;
            //indico que ya noe sta en la pila
			participante_apilado[*it] = false;
            //recuerdo el que estoy por sacar de la pila
			it2 = it;
			//lo saco de la pila
			it = pila.erase(it);
		}
		
		//mientras que tenga mas para sacar
		//y el ultimo que seque no era el participante en cuestion
		while( it != pila.end() && participante != *it2 )
		{
            //indico en que componente quedo ese participante
            componente[*it] = c;
            //indico que ya noe sta en la pila
			participante_apilado[*it] = false;
            //recuerdo el que estoy por sacar de la pila
			it2 = it;
			//lo saco de la pila
			it = pila.erase(it);
		}
		
		//ya complete la componente
		c++;
	}
}
